public class LinkedList {
      class  Node{
          public int val;
          public Node    prev;
          public Node     next;

           public Node(int val) {
                this.val = val;
           }

      }
      public Node head;
      public Node last;

     //头插法
     public void addFirst(int data){
         Node node=new Node(data);
         if(head==null){
             head=node;
             last=node;

         }
         node.next=head;
         head.prev=node;
         head=node;
     }

     //尾插法
     public void addLast(int data){
            Node node=new Node(data);
            if(head==null){
                head=node;
                last=node;
            }
            last.next=node;
            node.prev=last;
            last=node;
     }

     //任意位置插入,第一个数据节点为0号下标
     public void addIndex(int index,int data){
         //判断index合法性
         if(index<0||index>size()){
             throw new IndexOutOfException();
         }
         if(index==0){
             addFirst(data);
            return;

         }
         if(index==size()){
             addLast(data);
             return;
         }
         Node node=new Node(data);
         Node cur=findNode(index);
         node.next=cur;
         cur.prev.next=node;
         cur.prev=node;
         node.prev=cur.prev.prev;

     }
     public Node findNode( int  index){
         Node cur=head;
         while(index!=0){
             cur=cur.next;
             index--;
         }
         return cur;
     }
     //查找是否包含关键字key是否在单链表当中
     public boolean contains(int key){
         Node cur=head;
         while(cur!=null){
            if(cur.val==key){
                return true;
            }
             cur=cur.next;
         }
         return false;
     }
     //删除第一次出现关键字为key的节点
     public void remove(int key){
         Node cur = head;
         while (cur != null) {
             //开始删除了
             if(cur.val == key) {
                 //1. 删除的是头节点
                 if(cur == head) {
                     head = head.next;
                     //只有一个节点
                     if(head != null) {
                         head.prev = null;
                     }
                 }else {
                     //中间  尾巴
                     cur.prev.next = cur.next;
                     //不是尾巴节点
                     if(cur.next != null) {
                         cur.next.prev = cur.prev;
                     }else {
                         //是尾巴节点
                         last = last.prev;
                     }
                 }
                 return;
             }
             cur = cur.next;
         }

     }

     //删除所有值为key的节点
     public void removeAllKey(int key){
         Node cur = head;
         while (cur != null) {
             //开始删除了
             if(cur.val == key) {
                 //1. 删除的是头节点
                 if(cur == head) {
                     head = head.next;
                     //只有一个节点
                     if(head != null) {
                         head.prev = null;
                     }
                 }else {
                     //中间  尾巴
                     cur.prev.next = cur.next;
                     //不是尾巴节点
                     if(cur.next != null) {
                         cur.next.prev = cur.prev;
                     }else {
                         //是尾巴节点
                         last = last.prev;
                     }
                 }

             }
             cur = cur.next;
         }

     }
     //得到单链表的长度
     public int size(){
         int len=0;
         Node cur=head;
         while(cur!=null){
            len++;
             cur=cur.next;
         }
         return len;

     }
     public void display(){
         Node cur=head;
         while(cur!=null){
             System.out.println(cur.val+" ");
             cur=cur.next;
         }
     }
     public void clear(){
         while(head==null){
             return;
         }
     }

 }
